Куркчі В'ячеслав Андрійович
kourktchi@ukrtop.com
магістрант групи ПЗ-99, ФОТІ
научний керівник:
Ладиженський Юрій Валентинович

тема магістерскої роботы:
Паралельні алгоритми для рішення задач на графах.

     Для визначення поширеності досліжуваної теми, було проведено наступне дослідження: кільком популярним пошуковим сайтам в Інтернет був дан ряд запитів та зафіксована кількість знайденних по запиту сайтів.
     Резутьтати було зведено у таблицю.

     Дані на 19.03.2004

Запрос	Google	Rambler	Yandex	Meta-Ukraine
Теория графов	6210	11448	14138	1600
Задача о наибольшем независимом множестве	1	10346	43	1993
Задача о наибольшей клике	34	10346	98	117
Параллельные алгоритмы	4430	14044	702	2503
Параллельные алгоритмы на графах	191	1948	171	211
Graph theory	2020000	1774	2407	147
Maximum independent set	2520000	4763	77	1071
Maximum clique problem	31500	94	736	12
Parallel algorithms	1860000	3056	508	417
Parallel algorithms for graphs	227000	684	47	64
Neuro networks for graph theory	6760	41	90	7
Tabu search for graph theory	6760	10	730	0
Genetic algorithms for graph theory	49600	175	159	7
Greedy heuristic for graph theory	14800	15	133	0
Simulated annealing for graph theory	20600	85	636	5
NP-complete problems	121000	597	123	22
NP-completeness in graph theory	23300	68	44	1

     Із таблиці видно, що російськомовні запити краще за всіх оброблює пошуковий сервер Rambler, а англомовні - Google (зрозуміло, серед розглянутих). Також можно побачити, що англомовний Інтернет містить на декілька порядків більше сторінок, що містять ключові слова за темою.
     Зауважимо, що "сторінки, що містять ключові слова за темою" ще не означає "сторінки, що присвячені темі", через те, що слово граф має не одне значення в російській мові, а слово graph - ще більше значень в англійській (до того не тільки як именник, але й як дієслово). Це можна сказати і про інщі слова, які було вікористано в запитах. Тобто велика аількість сторінок, що містять шукані ключові слова, може говорити як про більш добре представлення теми, так і про більшу забрудненність інформаційного простору.
     Перевіриті яка саме з цих гіпотез правильна неможливо, через те, що обробити навіть короткий опис кількох сотень тисяч сторінок досить складно. Але в силу того, що кількість сторінок-відповідей на запити з більшою кількістю ключовіх слів або більш спеціальні запити виявилось на 2-3 порядки меньше, більш вероятною здається версія про забрудненість. З іншого боку, графи є дуже поширеними структурою даних та математичним апаратом, що використовуються в багатьох галузях науки и техніки. Але така різниця в числах викликає сумніви в тому, що це може бути причиною виявленого явища.

     Повертаючись до теми порівняння пошукових сайтів, скажемо, що кількісні оцінки результатів Rambler та Yandex колеблються відносно друг друга. Причому ці коливання не залежать ні від теми, ні від стутпеня ії спеціалізації. Единий вивод, який можно зробити у даному віпадку: для повишення вероятності знайти необхідну інформацію слід паралельно використовувати обидва сайти.
     Meta-Ukraine є "молодим" сайтом, але вже може составити конкуренцію іншим пошуковим серверам, правда, в обмеженому колі тем.

     Для виявлення динаміки поширеності теми було проведено повторне дослідження.

     Дані на 1.06.2004

Запрос	Google	Rambler	Yandex	Meta-Ukraine
Теория графов	6020	67742	15809	1840
Задача о наибольшем независимом множестве	7	58601	192	2004
Задача о наибольшей клике	32	4664	190	136
Параллельные алгоритмы	4090	76161	8047	2554
Параллельные алгоритмы на графах	174	6380	192	242
Graph theory	2330000	8170	2587	127
Maximum independent set	2580000	31932	78	716
Maximum clique problem	31400	237	8853	6
Parallel algorithms	1650000	19246	3591	286
Parallel algorithms for graphs	256000	3347	108	56
Neuro networks for graph theory	8740	54	159	1
Tabu search for graph theory	7480	123	11561	0
Genetic algorithms for graph theory	61000	334	502	3
Greedy heuristic for graph theory	15000	14	347	0
Simulated annealing for graph theory	21600	100	9184	3
NP-complete problems	111000	1701	446	8
NP-completeness in graph theory	22600	90	152	1

     При порівнянні таблиць видно, що ситуація в англомовній частині таблиці в цілому не змінилася: результати деяких запитів стали більше, інших - меньше, але більшість цих змін несуттєві через те, що вони не перевищюють 10%. Але деякі теми все-таки набирають популярність: це генетичні алгоритми, нейромережі та пошук табу. (за умовний показник популярности теми було принято максимум по запиту: по пошуковим серверам). Ці теми дійстно вважаються пріоритетними напрямками досліджень та розвиваються дуже швидко. В російськомовному Інтернеті можно побачити значний рост.
     Також сильно змінилася поведінка сайтів: посилилися позиції Rambler, и розширився англомовний пошук Yandex. Результати пошуку Meta-Ukraine практично не відрізняються.

     В заключення можно сказати, що при пошуку в Інтернеті англомовної інформації за нашою темою слід використовувати Google, а при російськомовному пошуку - Rambler. Yandex и Meta-Ukraine використовувати недоцільно, незважаючи на те, що Yandex в період між експериментами провів переіндексацію ресурсів Інтернет. Можливо, керівництво Yandex, вважає більш пріоритетними інші теми.

Повернутися до початку сторінки